enqueue(5)
                                        <- 1
Q = [ 5][  ][  ][  ][  ][  ][  ][  ]
--------------------------------------------
enqueue(-2)
                                        <- 2
Q = [ 5][-2][  ][  ][  ][  ][  ][  ]

텅 비어있는 큐에 5라는 값을 삽입하면, 위와 같이, 가장 왼쪽 빈칸에 5가 들어가게 된다.
(만약, 큐 자료 구조를 세워서 그렸다고 가정한다면, 이는 가장 아래쪽 빈칸이 될 것이다.)
그런 다음, -2라는 값을 큐에 삽입하면, 5가 들어간 바로 다음 칸에, -2가 들어가게 된다.

스택에서 pop() 이라고 불리는 삭제(delete) 연산의 경우, 큐에서는 dequeue() 라고 부른다.

dequeue() # 5
                                        <- 1
Q = [-2][  ][  ][  ][  ][  ][  ][  ]
--------------------------------------------
enqueue(10)
                                        <- 2
Q = [-2][10][  ][  ][  ][  ][  ][  ]
--------------------------------------------
dequeue() # -2
                                        <- 3
Q = [10][  ][  ][  ][  ][  ][  ][  ]

위 상황에 이어서, 값을 삭제하면, 선입선출 규칙에 따라, 먼저 삽입된 값 5가 삭제된다.
(이 과정을 그대로 스택에서 처리했다면, 더 나중에 삽입된 값인 -2가 삭제되었을 것이다.)
이 상태에서 다시 10이라는 값을 삽입하면, -2가 있는 칸 바로 뒤에 10이 들어가게 된다.
여기서 다시, 삭제 연산을 수행하면, 저장된 값 중 가장 먼저 들어온 값인 -2가 삭제된다.

큐의 삽입/삭제 연산은, 이렇게, 뒤로 삽입하고, 앞에 있는 원소를 삭제하는 식으로 수행된다.

이전 수업에서도 언급했듯, 스택과 큐의 연산 수행 규칙을 생물에 빗대어 표현할 수 있다.

스택의 경우, 바닷속에 사는, 입으로 먹어서, 입으로 배설하는 말미잘에 비유할 수 있다.
큐의 경우, 입으로 먹어서, 뒤(?) 로 배설하는, 말과 같은 평범한 동물에 비유할 수 있다.

1-2. 연산에 필요한 정보

이번에는, 이러한 enqueue(), dequeue() 연산을 수행할 때, 어떤 정보가 필요한지 살펴보자.

스택의 경우, 가장 마지막에 저장된 값(top) 의 인덱스만 알면, 연산을 수행할 수 있다.
왜냐하면, 값을 삽입하거나 삭제하면서 반환할 때 필요한 인덱스가 모두 같기 때문이다.

이러한 스택과는 다르게, 큐는, 값이 삽입될 위치와 삭제될 위치의 인덱스를 모두 필요로 한다.

enqueue() 연산의 경우, 몇 개의 값이 저장되어 있는지를 알고 있어야 수행할 수 있다.
다음으로, dequeue() 연산의 경우, 반환할 값의 인덱스를 알고 있어야 수행할 수 있다.
이는, 순서대로 삽입되고, 삽입된 순서 그대로, 차례대로 삭제되는 큐의 특징 때문이다.
정리하자면, 큐는 삽입/삭제 연산용 인덱스를 따로 관리하는 자료 구조라고 할 수 있다.

enqueue() 연산은 원소를 뒤에 추가하므로, 리스트의 append() 와 같다고 생각할 수도 있다.

이렇게, enqueue() 를 append() 로 생각하면, 삽입할 위치를 따로 관리할 필요가 없어진다.

dequeue() 연산은, enqueue() 와는 다르게, 처리할 대상의 인덱스가 무조건 필요한 연산이다.

이 때, dequeue() 연산의 대상인, 큐의 맨 앞부분을 가리키는 인덱스를 ‘front’ 라고 부른다.

이렇게, 큐의 앞부분은 ‘front’ 라 부르며, 반대편에 해당하는 뒷부분은 보통 ‘rear’ 라고 부른다.

다시 말해, ‘rear’ 에는 enqueue() 연산, ‘front’ 에서는 dequeue() 연산이 처리되는 것이다.

참고 : 실제 교수님 강의 화면 필기 내용

screen note 1

2. 직접 구현해보기

이렇게 큐의 특징과 제공하는 연산들에 대해 알아봤으니, 이번에는, 큐를 클래스로 구현해보자.

우선, 파이썬 문법에 따라 클래스를 선언할 것이며, 클래스 이름은 ‘Queue’ 라고 할 것이다.
실제로 정보를 저장할 공간이 필요한데, 이는 ‘items’ 라는 이름의 리스트로 구현할 것이다.
(저장 공간이 리스트이기 때문에, enqueue() 를 구현할 때, append() 를 활용할 수 있다.)
dequeue() 를 구현하기 위해, ‘front_index(‘front’ 의 인덱스)’ 라는 변수도 사용할 것이다.
즉, 선언할 클래스는 ‘items’ 리스트와 ‘front_index’ 변수를 멤버 변수로 갖게 되는 것이다.

2-1. 코드 작성하기

이렇게, 큐 자료 구조에 대한 클래스를 어떻게 구현할지 정했으니, 이를 직접 코드로 작성해보자.

class Queue:
    def __init__(self):
        self.items = [] # 빈 리스트
        self.front_index = 0

    def enqueue(self, val):
        self.items.append(val)

    def dequeue(self):
        if self.front_index == len(self.items):
            print("Q is empty")
        else:
            x = self.items[front_index]
            self.front_index += 1
            return x

파이썬으로 클래스를 작성할 때, 맨 처음으로 작성해야 하는 것은, 생성자 메서드 __init__() 이다.

우선, 생성자 내부에, 멤버 변수 ‘items’ 를 선언한 후, 이를, 빈 리스트로 초기화할 것이다.
이렇게, 저장 공간이 준비되었으니, 다음으로는, ‘front_index’ 를 0으로 초기화하면 된다.

이렇게, 클래스 생성자 작성이 끝났으니, 이제, enqueue() 연산을 처리할 메서드를 구현해보자.

‘클래스를 통해 생성된 객체’ 를 가리키는 ‘self’ 와 삽입하려는 값인 ‘val’ 을 인자로 받는다.
입력된 값은 ‘items’ 리스트의 뒷부분에 삽입되어야 하므로, append() 메서드를 사용한다.

여기서 중요한 것은 dequeue() 연산을 어떤 식으로 처리하느냐인데, 하나씩 차근차근 살펴보자.

연산을 수행할 대상, 즉, ‘클래스를 통해 생성된 객체’ 를 가리키는 ‘self’ 를 인자로 받는다.
그리고, 해당 객체의 ‘front_index’ 에 있는 값을 삭제한 후, 그 값을 그대로 반환하면 된다.

이 때, 객체의 ‘front_index’ 와 ‘items’ 리스트의 길이가 같다면, 그런 경우는 따로 처리할 것이다.

‘큐가 비어있음을 알리는 문구’ 를 출력하도록 할 텐데, 이유는 아래에서 예시와 함께 살펴보자.

2-2. dequeue() 보충

우선, 큐에 5, -2, 10이 저장되어 있다고 가정했을 때, ‘front_index’ 는 5를 가리키고 있을 것이다.

Q = [ 5][-2][10][  ][  ][  ][  ][  ]
     fi

front_index = 0, len(items) = 3

여기서 dequeue() 연산을 수행하면, ‘items’ 의 길이와 ‘front_index’ 의 값이 달라질 것이다.
아무것도 하지 않았을 경우, ‘items’ 의 길이는 3, ‘front_index’ 는 0으로, 값이 서로 다르다.
이는, 큐에 원소가 있다는 것을, 다르게 말하면, dequeue() 할 원소가 있다는 것을 의미한다.

이제, 연산을 실제로 처리하기 위해, if 문 뒤에 else 문을 추가해, 값을 삭제/반환하도록 할 것이다.

Q = [ 5][-2][10][  ][  ][  ][  ][  ]
         fi

front_index = 1, len(items) = 3

이 때, ‘items’ 의 ‘front_index’ 에 있는 값을 따로 변수에 저장해뒀다가, 삭제/반환하면 된다.
여기서 ‘삭제한다.’ 는 ‘큐의 원소가 아니다.’ 이므로, 실제로는 원소를 삭제하지 않아도 된다.
이를 엄청나게 단순하게 처리할 수 있는데, 바로, ‘front_index’ 의 값을 1 증가시키는 것이다.
현재 예시 상황에서 dequeue() 를 수행하면, ‘front_index’ 는 1이 되어, -2를 가리키게 된다.
이렇게 하면, ‘front_index’ 가 ‘다음 dequeue() 연산에서 반환해야 할 값’ 을 가리키게 된다.
이렇게 삭제 작업을 마친 후에는 앞에서 저장해두었던 변수를 그대로 반환하기만 하면 된다.

이번에는, “‘front_index’ 가 ‘items’ 의 길이와 같을 때 = 큐가 비어있는 상태” 인 이유를 알아보자.

Q = [ 5][-2][10][  ][  ][  ][  ][  ]
             fi

front_index = 2, len(items) = 3
--------------------------------------------
Q = [ 5][-2][10][  ][  ][  ][  ][  ]
                 fi

front_index = 3, len(items) = 3

dequeue() 연산을 한 번 더 수행하면, -2가 반환되고, ‘front_index’ 는 10을 가리키게 된다.
이 때, dequeue() 연산을 추가로 수행하면, 10이 반환되고, ‘front_index’ 의 값은 3이 된다.
위에서 볼 수 있듯, 이 상태에서 다시 dequeue() 연산을 수행하려고 해도, 반환할 값이 없다.

이렇게, ‘front_index’ 의 값과 ‘items’ 의 길이가 같은 경우, ‘front_index’ 는 빈칸을 가리키게 된다.

이는, ‘저장된 값 중 가장 먼저 들어온 원소가 없다.’, 다시 말해, ‘큐는 비어있다.’ 를 의미한다.
이는 원소를 삭제하는 대신에, ‘front_index’ 로 값의 유효 범위를 관리해서 생기는 상황이다.
이러한 이유로, 큐가 비어있다는 것을 알리는 메시지를 출력하고, ‘None’ 을 반환하는 것이다.

참고 : 실제 교수님 강의 화면 필기 내용

screen note 2

3. 활용 예시 살펴보기

마지막으로, 큐에서 제공하는 연산을 좀 더 명확하게 이해하기 위해, 예제 하나를 더 살펴볼 것이다.

아래에서 살펴볼 예시는, 꽤 유명한 문제 중 하나인 ‘요세푸스 문제(Josephus Problem)’ 다.
위키피디아, 나무위키 등의 인터넷 백과사전을 찾아보면, 좀 더 자세한 내용을 확인할 수 있다.

3-1. 요세푸스 문제 설명

요세푸스 문제는, 어떤 전투 중에 군인들이 동굴에 갇혀 적들에게 포위된 상황에서 만들어진 문제다.

군인들은, 적에게 붙잡혀서 비굴하게 항복하는 대신, 죽을 순서를 정한 후에 자살하기로 했다.
물론, 마지막까지 살아남은 건 이 문제를 역사에 남긴 요세푸스였다. (그는 적에게 항복했다.)
역사에 관한 이야기는 여기까지만 하고, 간단한 예시와 함께, 문제를 좀 더 자세하게 살펴보자.

1번부터 6번까지, 총 6명의 군인이 있고, 순서를 두 번 건너뛸 때마다 사람이 죽는다고 가정해보자.

n = 6, k = 2

-> 1 -> 2 -> 3 -> 4 -> 5 -> 6 ─┐
   o    x    o    x    o    x  │
┌──────────────────────────────┘
6 -> 1 -> 3 -> 5 -> 1
x    o    x    o    x

여기서, n은 군인의 수, 즉, 6이며, k는 죽을 사람이 정해지는 건너뛰기의 횟수, 즉, 2가 된다.
우선, 건너뛰기를 시작하려면 기준 번호가 있어야 하므로, 1번 사람부터 시작한다고 가정한다.
예시 상황을 기준으로, 맨 처음에는 2번 군인이 죽고, 그다음에는 4번, 6번 군인이 죽게 된다.
6번 군인 다음 순서에는 사람이 없으므로, 다시 1번 군인부터 순서대로 건너뛰기를 하면 된다.
현재까지 살아남은 1, 3, 5번 군인을 기준으로 건너뛰기를 이어서 하면, 3번 군인이 죽게 된다.
마지막으로, 직전에 죽은 3번 군인의 다음 순서인 5번 군인을 건너뛰고, 1번 군인이 죽게 된다.
결국, 예시 상황에서는, 5번 군인만 끝까지 살아남게 되면서, 나머지 군인들은 전부 죽게 된다.

이렇게, 대상의 수 n과 조건값 k가 주어졌을 때, 마지막에 남는 번호를 찾는 것이 요세푸스 문제다.

n = 9, k = 3

-> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 ─┐
   o    o    x    o    o    x    o    o    x  │
┌─────────────────────────────────────────────┘
9 -> 1 -> 2 -> 4 -> 5 -> 7 -> 8 ─┐
x    o    o    x    o    o    x  │
┌────────────────────────────────┘
8 -> 1 -> 2 -> 5 -> 7 ─┐
x    o    o    x    o  │
┌──────────────────────┘
7 -> 1 -> 2 -> 7 ─┐
o    o    x    o  │
┌─────────────────┘
7 -> 1 -> 7
o    o    x

다른 값, 예를 들어, n = 9, k = 3 을 대입하면, 세 번 건너뛸 때마다, 한 명씩 죽게 되는 것이다.
그러면, 3, 6, 9, 4, 8, 5, 2, 7번 순서로 군인들이 죽게 되면서, 1번 군인이 마지막에 남게 된다.

3-2. 요세푸스 문제 풀이

요세푸스 문제가 어떤 문제인지 알았으니, 이번에는 이러한 문제를 푸는 함수의 구성을 파악해보자.

def josephus(n, k):
    ...
    return survivor

n과 k를 인자로 받아, 끝까지 남는 번호를 반환하는 함수이며, 이름은 ‘Josephus’ 라고 하자.
요세푸스 문제를 푸는 방법은 여러 가지가 있으며, 좀 전에 배운 큐를 활용하는 방법도 있다.
가장 효율적인 방법은 아니지만, 문제 상황을 그대로 시뮬레이션할 수 있다는 것이 장점이다.

우선, 위에서 살펴봤던 n = 9, k = 3 인 경우라고 가정하고, 큐를 활용하면 어떻게 되는지 살펴보자.

Q = [1][2][3][4][5][6][7][8][9]
     ↓

시작할 때, 큐에는 총 9개의 번호가 들어 있고, k = 3, 즉, 3번 건너뛸 때마다 번호가 삭제된다.
처음에 삭제되어야 하는 번호는 3이지만, 큐의 특성상, 가장 먼저 dequeue() 되는 값은 1이다.
이처럼, 큐 자료 구조는 선입 선출 규칙을 따라야 하므로, 원하는 값을 바로는 삭제할 수 없다.
때문에, 삭제할 값이 나오기 전에 마주치는 원소들은 삭제하자마자, 바로 다시 삽입해야 한다.

현재 k의 값은 3이므로, k번째 이전까지의 (k - 1) 개, 즉, 3 - 1 = 2 개를 다시 enqueue() 하면 된다.

Q = [1][2][3][4][5][6][7][8][9][1][2]
     ↓  ↓  ↓                    ↑  ↑
     o  o  x                    o  o

문제 상황에 비유하자면, 1번 군인은 죽지 않았으니, 다시 건너뛰기 대기열에 들어가는 것이다.
그러면, 1번과 마찬가지로 2번도 다시 enqueue() 되므로, 큐 맨 뒤쪽에 1번과 2번이 추가된다.
다음에 dequeue() 되는 번호인 3의 경우, 다시 enqueue() 하지 않으면 그대로 값이 제거된다.
이렇게, 삭제할 원소 앞에 있던 원소들은, 그대로 다시 삽입되어, 큐의 뒤쪽으로 이동하게 된다.

건너뛰기를 이런 식으로 처리하면, 원하는 값만 골라 삭제하면서, 다른 값을 그대로 유지할 수 있다.

Q = [4][5][6][7][8][9][1][2][4][5][7][8]
     ↓  ↓  ↓  ↓  ↓  ↓        ↑  ↑  ↑  ↑
     o  o  x  o  o  x        o  o  o  o

Q = [1][2][4][5][7][8][1][2][5][7]
     ↓  ↓  ↓  ↓  ↓  ↓  ↑  ↑  ↑  ↑
     o  o  x  o  o  x  o  o  o  o

                    ፧

이렇게, 맨 처음에는 3번이 삭제되며, 이후, 같은 과정을 반복하면 1, 2, 4, 5, 7, 8이 남게 된다.
큐에 원소가 하나만 남을 때까지, 이 과정을 그대로 반복하면, 마지막에 남은 번호가 답이 된다.

요세푸스 문제 관련 함수의 실제 코드는 강의 노트에 있으니, 강의 노트와 구름을 참조하길 바란다.

3-3. 덱(Deque)

다음으로, 이러한 스택과 큐를 합친 형태의 순차적인 자료 구조인 ‘덱(Deque)’ 에 대해서 알아보자.

영어로 표기할 때는, 큐에서 제공하는 삭제 연산의 이름과 같은 ‘dequeue’ 로 표기하기도 한다.
‘스택과 큐를 합쳤다.’ 라는 표현은, ‘둘의 삽입/삭제 연산을 모두 수행할 수 있다.’ 를 의미한다.

여기서 ‘Deque’ 은 ‘Double-Ended-Queue’ 의 줄임말이며, 이는 ‘양쪽으로 끝나는 큐’ 라는 뜻이다.

deque = [1, 2, 3, 4]

deque.append(5)     # [1, 2, 3, 4, 5]
deque.pop()         # [1, 2, 3, 4]

deque.appendleft(5) # [5, 1, 2, 3, 4]
deque.popleft()     # [1, 2, 3, 4]

이름에서 알 수 있듯, 덱은, 큐의 삽입/삭제 연산을 저장 공간의 앞뒤 양쪽에서 수행할 수 있다.
이 때, 평범하게 큐처럼 삽입하면 append(), 반대 방향으로 삽입하면 appendleft() 라고 한다.
비슷한 예로, 평범하게 스택처럼 삭제하면 pop(), 반대 방향으로 삭제하면 popleft() 라고 한다.

위에서 했던 것처럼 덱을 직접 구현할 수도 있지만, 파이썬의 경우, 이러한 덱을 자체적으로 제공한다.

온라인 Q&A 수업에서, 이러한 덱을 어떻게 사용하는지와 활용할 수 있는 예제에 대해 다룰 것이다.

참고 : 실제 교수님 강의 화면 필기 내용

screen note 3

20220214 - 표기 수정(메소드 -> 메서드)

Buy me a coffee

# 컴퓨터 공학# 자료 구조# 알고리즘